#include "main/utils.h"
using namespace std;

vector<pair<int, int>> mergeIntervals(vector<pair<int, int>> intervals) {
  sort(intervals.begin(), intervals.end());
  vector<pair<int, int>> ret;
  ret.push_back(*intervals.begin());
  for (int i = 1; i < intervals.size(); ++i) {
    auto back = ret.back();
    if (intervals[i].first < back.second) {
      if (intervals[i].second > back.second) {
        pair<int, int> new_back = make_pair(back.first, intervals[i].second);
        ret.pop_back();
        ret.push_back(new_back);
      }
    } else {
      ret.push_back(intervals[i]);
    }
  }
  return ret;
}

int main() {
  vector<pair<int, int>> intervals = {{1, 3}, {4, 5}, {8, 10}, {2, 6}, {9, 12}, {15, 18}};
  auto ret = mergeIntervals(intervals);
  printVec("o74", ret);

  return 0;
}
